package algo.graph;

import java.util.Stack;

public abstract class Path {
	protected Graph g;
	protected int s;
	protected int[] precedents;
	
	public Path(Graph g, int s) {
		this.g = g;
		this.s = s;
	}

	protected abstract boolean marked(int v);

	public Stack<Integer> pathTo(int v) {
		Stack<Integer> stack = new Stack<Integer>();
		stack.push(v);
		while (true) {
			if (v == s)
				break;
			v = precedents[v];
			stack.push(v);
		}
		if (s != v)
			stack.push(s);
		return stack;
	}

	public String pathToStr(int v) {
		Stack<Integer> stack = pathTo(v);
		String str = "";
		while (!stack.isEmpty()) {
			str += stack.pop() + " ";
		}
		return str;
	}
}
